// 二维数组中查找
// 二维数组是从左到右，从上到下依次递增
//
// 思路：
// 	查找的时候选择其中一个点
// 	如果要找的数大于该点就表示在下面(包括既是右边又是下边的区域)或者右边(包括既是右边又是下边的区域)
// 	如则就表示在左边或者下边
// 	如果相等就表示找到了
// 	缺点：有重复区域

// 	这个随机选取的点很重要
// 	如果是选择中间区域的点就意味着想要查找的数字相对于当前位置可能出现在两个区域中，并且这两个区域还有重叠
//
// 	假如选取右上角的作为基准点
// 	大于：就剔除基准点所在的行
// 	小于：剔除基准点所在的列
// 	每次都能剔除一行或者一列，知道找到或者找不到
// 	
// 	也可以选取左下角，但是不能选择左上角和右下角，这样的话不能保证每次都能剔除一行或者一列

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define ROW 4
#define COL 4

void find(int arr[ROW][COL], int num)
{
	if(NULL == arr) {
		printf("Error Input!\n");
		return;
	}

	printf("The Num Is %d\n", num);

	int row = 0;
	int col = COL - 1;
	while(row < ROW && col >= 0) {
		int base = arr[row][col];
		if(base > num)
			--col;
		if(base < num)
			++row;
		if(base == num) {
			printf("Found It : 第%d行, 第%d列\n", row + 1, col + 1);
			return;
		}
	}
	printf("Not Found!\n");
	return;
}

int main()
{
	int arr[][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
	int i = 0, j = 0;
	for(i = 0; i < ROW; ++i) {
		for(j = 0; j < COL; ++j) {
			printf("%4d", arr[i][j]);
		}
		printf("\n");
	}
	find(arr, 0);

	return 0;
}












